package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-26 14:24
 * @Description: Backpack$背包问题-lintCode92
 *
 * 给定n个整数，分别是正整数A0,A1,A2,...,An-1
 * 一个正整数Target
 * 有多少种组合加起来是Target
 * 每个Ai只能用一次
 *
 * eg:
 *  输入：A=[1,2,3,3,7],Target=7
 *  输出：2(7=7,1+3+3)
 *
 *
 *
 * 【解析】
 *  n个正整数：A0,A1,A2,...,An-1->N个物品的重量为A0,A1,...,An-1
 *
 *  要求和是Target -> 正好装满一个载重为Target的背包
 *
 *  背包问题
 *
 *  不同Backpack,需要求出有多少中组合和是Target,而不是能不能拼出Target
 *
 *  当然，如果能知道这N个物品有多少种方式拼出0，有多少种方式拼出1,...,有
 *  多少种方式拼出Target,即得到答案
 *
 *
 *    step 1:确定状态
 *          最后一步：需要直到N个物品多少中方式拼出重量W(W=0,1,2,...,Target)
 *                  最后一步：最后一个物品（重量为An-1）是否进入背包
 *
 *           情况一：如果前N-1个物品能拼出W
 *           情况二：如果前N-1个物品能够拼出W-An-1,再加上最后的物品An-1,拼出W
 *              情况一的个数+情况二的个数 = 用前N个物品拼出W的方式
 *
 *          子问题：
 *              要求前N个物品能不能拼出重量0,1,2,...,Target
 *              需要知道前N-1个物品多少方式拼出0,1,2,..,Target
 *          状态：设f[i][w]=用前i个物品有多少种方式拼出重量w
 *
 **
 *     step 2:转移方程
 *          设f[i][w] = 用前i个物品有多少种方式拼出重量w
 *              f[i][w] = f[i-1][w] + f[i-1][w-A_(i-1)]
 *     用前i个物品多少种方式拼出重量w  用前i-1个物品多少种方式拼出重量w  用前i-1个物品多少中方式拼出w-A(i-1),在加上第i个物品
 *
 *     step 3:初始条件和边界情况：
 *          初始条件：
 *              f[0][0]=1:0个物品可以有一种方式拼出重量0
 *              f[0][1..M]=0:0个物品不能拼出大于0的重量
 *          边界情况：
 *              f[i-1][w-A(i-1)]只能在w>=A(i-1)时使用
 *
 *     step 4:计算顺序
 *          初始化f[0][0],f[0][1],...,f[0][M]
 *          计算前1个物品能拼出那些重量：f[1][0],f[1][1],...,f[1][M]
 *          计算前2个物品能拼出那些重量：f[2][0],f[2][1],...,f[2][M]
 *          ...
 *          计算前N个物品能拼出那些重量：f[N][0],f[N][1],...,f[N][M]
 *      答案：f[N][Target]
 *
 *      时间复杂度：O(NTarget),空间复杂度：数组大小，优化后可以为O(Target)
 *
 *
 *      进一步的空间优化：
 *          f[i][w] = f[i-1][w] + f[i-1][w-A(i-1)]
 *
 *          实际编程中可以进一步优化：通常开两行二维的一个滚动数组，但是终极优化还可以只开一个一维数组优化空间
 *
 *         从右向左计算，覆盖旧值，变为一维数组,新值填充旧值
 *         f[i][w] = f[i-1][w] + f[i-1][w-A(i-1)]可以只开一个数组，按照f[i][Target],...,f[i][0]的顺序更新
 *
 */
public class BackpackV {


	int backPackV(int[] item,int T){
		int i,j;
		int n = item.length;
		if(n==0){
			return 0;
		}

		int[][] f = new int[n+1][T+1];
		f[0][0] = 1;
		for (i=1;i<=T;i++){
			f[0][i]=0;
		}

		// f[i][w] = f[i-1][w] + f[i-1][w-A_(i-1)]
		for (i=1;i<=n;i++){
			for(j=0;j<=T;j++){

				f[i][j] += f[i-1][j];


				if(j>=item[i-1]){
					f[i][j]+=f[i-1][j-item[i-1]];
				}

			}
		}
		return f[n][T];
	}

	int backPackV2(int[] item,int T){

		int i,j;
		int n = item.length;
		if(n==0){
			return 0;
		}

		int[] f = new int[T+1];
		f[0] = 1;
		for(i=1;i<=T;++i){
			f[i]=0;
		}

		for(i=1;i<=n;++i){
			//重点！！！， 优化空间，从右向左，优化，T -> 0
			for(j=T;j>=0;j--){
				//f[j] + f[j-A[i-1]] ==> f`[j]
				if(j>=item[i-1]){
					//得出新f[j],cover f[j]
					f[j] += f[j-item[i-1]];
				}
			}
		}
		return f[T];

	}

	public static void main(String[] args) {
		int[] item = {1,3,3,7};
		int m = 7;
		BackpackV instance = new BackpackV();
		System.out.println(instance.backPackV(item,m));
	}

}
